#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2022/6/7 13:41
# @Software: PyCharm
# @File    : l120_triangle.py


class Solution:
    def __init__(self):
        '''
        给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

        例如，给定三角形：

        [
             [2],
            [3,4],
           [6,5,7],
          [4,1,8,3]
        ]
        自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
        https://leetcode-cn.com/problems/triangle/
        '''
        pass


    def minimumTotal2(self, triangle) -> int:
        '''
        思路：从最后第二层开始，每次保存当前元素与下一行2个元素和的最小值
        :param triangle:
        :return:
        '''
        count = len(triangle)
        if count <= 0:
            return 0
        li = triangle.pop()
        while triangle:
            tmp = []
            for i, v in enumerate(triangle[-1]):
                min_v = min(v + li[i], v + li[i + 1])
                tmp.append(min_v)
            li = tmp
            triangle.pop()
        # print(li)
        return li[0]


    def minimumTotal(self, triangle: list[list[int]]) -> int:
        dp = [0] * (len(triangle) + 1)
        for i in range(len(triangle) - 1, -1, -1):
            for j in range(0, i + 1):
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
        return dp[0]


if __name__ == '__main__':
    s = Solution()
    li = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
    li = [[-1], [2, 3], [1, -1, -3]]
    res = s.minimumTotal(li)
    print(res)
    res = s.minimumTotal2(li)
    print(res)
